The Randomness Complexity of Parallel Repetition

Kai-Min Chung
 

Monday September 26, 2011
4:00 PM, 5130 Upson Hall

Abstract:

Consider a $m$-round interactive protocol with soundness error $1/2$. How much extra randomness is required to decrease the soundness error to $\delta$ through parallel repetition? Previous work, initiated by Bellare, Goldreich and Goldwasser, shows that for public-coin interactive protocols with statistical soundness, $m \cdot O(\log (1/\delta))$ bits of extra randomness suffices. In this work, we initiate a more general study of the above question.

- We establish the first derandomized parallel repetition theorem for public-coin interactive protocols with *computational soundness* (a.k.a. arguments). The parameters of our result essentially matches the earlier works in the information-theoretic setting.

- We show that obtaining even a sub-linear dependency on the number of rounds $m$ (i.e., $o(m) \cdot \log(1/\delta)$) is impossible in the information-theoretic, and requires the existence of one-way functions in the computational setting.

- We show that non-trivial derandomized parallel repetition for private-coin protocols is impossible in the information-theoretic setting and requires the existence of one-way functions in the computational setting.

These results are tight in the sense that parallel repetition theorems in the computational setting can trivially be derandomized using pseudorandom generators, which are implied by the existence of one-way functions.

This is a joint work with Rafael Pass.